import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 查找树中p、q节点的最近公共祖先②
 * User: xwl
 * Date: 2023-05-22
 * Time: 11:26
 */

class TreeNode2 {
    int val;
    TreeNode2 left;
    TreeNode2 right;
    TreeNode2(int x) { val = x; }
}

public class Test1_2 {

    /**
     * 使用栈查找p、q节点的最近公共祖先
     * @param root:树的根节点
     * @param p:待查找节点1
     * @param q:待查找节点1
     * @return null:没有公共祖先
     */
    public TreeNode2 lowestCommonAncestor(TreeNode2 root, TreeNode2 p, TreeNode2 q) {
        // 向俩个栈中存储数据
        Deque<TreeNode2> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode2> stack2 = new LinkedList<>();
        getPath(root,p,stack2);
        // 走差值步
        int dValue = stack1.size() - stack2.size();
        if (dValue > 0) {
            while (dValue > 0) {
                stack1.pop();
                dValue--;
            }
        }else if (dValue < 0) {
            while (dValue < 0) {
                stack2.pop();
                dValue++;
            }
        }
        // 实现
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() == stack2.peek()) {
                return stack1.peek();
            }
            stack1.pop();
            stack2.pop();
        }
        //
        return null;
    }

    /**
     * 找到从根节点到指定节点node路径上的所有的节点，并存放到栈中
     * @param root:树的根节点
     * @param node:待查找的节点
     * @param stack:用来存放的栈
     * @return true: 找到了 false:没找到
     */
    public boolean getPath(TreeNode2 root, TreeNode2 node, Deque<TreeNode2> stack) {
        // 讨论树为空或者待查找节点为空的情况
        if (root == null || node == null) {
            return false;
        }
        stack.push(root);
        // 找到
        if (node == root) {
            return true;
        }
        // 递归实现
        boolean left = getPath(root.left,node,stack);
        if (left == true) {
            return true;
        }
        boolean right = getPath(root.right,node,stack);
        if (right == true) {
            return true;
        }
        // 没找到的情况
        stack.pop();
        // 没找到返回
        return false;
    }
}
